package binarysearch;

import org.junit.Test;

import java.util.Arrays;

public class FindFirstAndLastPositionOfElementInSortedArray34 {
    @Test
    public void test() {
        System.out.println(Arrays.toString(searchRange(new int[]{5,7,7,8,8,10}, 8)));
        System.out.println(Arrays.toString(searchRange(new int[]{5,7,7,8,8,10}, 6)));
        System.out.println(Arrays.toString(searchRange(new int[]{5,7,7,8,8,10}, 5)));
        System.out.println(Arrays.toString(searchRange(new int[]{5,7,7,8,8,10}, 0)));
    }

    public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        // find left boundary
        // eg. nums = [1, 3, 3, 5], target=3.
        // 1st loop: left=0, right=3, mid=1; nums[mid]=target, then right=mid-1=0;
        // 2nd loop: left=0, right=0, mid=0; nums[mid]<target, then left=mid+1=1;
        // no 3rd loop. left=1 is left boundary
        // anyway, if target=4,
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                right = mid - 1;
            }
        }
        // not found
        if (left >= nums.length || // target > nums[length-1]
                nums[left] != target) { // target not in nums
            return new int[]{-1, -1};
        }

        int[] range = new int[2];
        range[0] = left;

        // find right boundary
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        range[1] = right;
        return range;
    }
}
